# 139. 单词拆分
# https://leetcode-cn.com/problems/word-break/



class Solution:
    def wordBreak(self, s, wordDict):
        if not wordDict:
            return False
        max_len = max(wordDict, key=lambda t:len(t))
        res_map = {}
        return self.getResult(s, 0, len(max_len), wordDict, res_map)


    def getResult(self, s, start, max_len, words, res_map):
        if start == len(s):
            return True
        if res_map.__contains__(start):
            return res_map.get(start)
        i = start
        while i < start + max_len and i < len(s):
            if s[start: i+1] in words:
                if self.getResult(s, i+1, max_len, words, res_map):
                    res_map[start] = True
                    print(res_map)
                    return True
            i += 1
        res_map[start] = False
        return False

# print(Solution().wordBreak('leetcode', ["leet", "code"]))
# print(Solution().wordBreak('aaaaaaa', ["aaaa","aaa"]))
print(Solution().wordBreak('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab', ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]))
